package greddy;
import java.util.*;
public class _14_763_划分字母区间 {
    public static List<Integer> partitionLabels(String s) {
    	List<Integer> list = new ArrayList<>();
    	Map<String,Integer> map = new HashMap<>();
    	String key = "";
    	// 统计每个字母最远出现的下标
    	for(int i = 0; i < s.length(); i++) {
    		key = String.valueOf(s.charAt(i));
    		map.put(key, i);
    	}
    	// 区间开始位置 用于保存每个区间开始位置，最终统计区间长度
    	int actionIndex = 0;
    	// 区间内元素最远的下标位置
    	int lastIndex = 0;
    	int value = 0; // 当前元素最后一次出现的位置
    	for(int i = 0; i < s.length(); i++) {
    		// 拿到当前字母最远出现位置
    		value = map.get(String.valueOf(s.charAt(i)));
    		// 更新最远区间
    		lastIndex = Math.max(lastIndex, value);
    		// 到达最远区间
    		if(i == lastIndex) {
    			list.add(lastIndex - actionIndex + 1);
    			actionIndex = lastIndex + 1;
    		}
    	}
    	
    	return list;
    }
    
    public static void main(String[] args) {
    	String s = "a";
    	System.out.println(partitionLabels(s));
	}
}
